package dp

// 每一回合，任选两个石头，粉碎，相互抵消
// 最多剩下一块石头，返回最小的可能重量
func lastStoneWeightII(stones []int) int {
	// 背包总重量是sum
	sum := 0
	for _,v :=range stones {sum+=v}
	// 将重量尽量分为相同的两堆  
	// 重量和价值=stone[i]  背包容量sum/2 ?
	// dp[j] 表示总重量/容量为j的背包，最多背dp[j]这么重的石头
	//  dp[j] = max(dp[j], dp[j-weight[i]]+value[i]) 
	// 初始化  
	dp := make([]int, sum+1)
	target := sum/2
	for i:=0;i<len(stones);i++{
		for j:=target;j>=stones[i];j-- {
			if dp[j] < dp[j-stones[i]]+stones[i] {
				dp[j] = dp[j-stones[i]]+stones[i]
			}
		}
	}
	return sum-dp[target]-dp[target]
}
